package com.yt.ds.chapter4;

import com.yt.ds.chapter2.MinPQ;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @Author: lzf
 * @Date: 2020/8/3 16:16
 * @Description: 最小生成树的Prim算法的延时实现
 */
public class LazyPrimMST implements MST {
    private boolean[] marked;       // 最小生成树的顶点
    private Queue<Edge> mst;        // 最小生成树的边
    private MinPQ<Edge> pq;         // 横切边(包括失效的边)

    public LazyPrimMST(EdgeWeightedGraph graph) {
        pq = new MinPQ<>();
        mst = new LinkedList<>();
        marked = new boolean[graph.getVertexNum()];
        visit(graph, 0);

        while (!pq.isEmpty()) {
            Edge edge = pq.delMin();
            int v = edge.either();
            int w = edge.other(v);

            if (marked[v] && marked[w]) {
                continue;
            }
            mst.add(edge);
            if (!marked[v]) {
                visit(graph, v);
            }
            if (!marked[w]) {
                visit(graph, w);
            }
        }
    }

    /**
     * 描述：标记顶点V 并将所有连接V和未被标记顶点的边加入pq
     *
     * @param graph 权重图
     * @param v     顶点v
     * @return "void"
     * @date: 2020/8/3 16:39
     */
    private void visit(EdgeWeightedGraph graph, int v) {
        marked[v] = true;
        for (Edge edge : graph.adj(v)) {
            int w = edge.other(v);
            if (!marked[w]) {
                pq.insert(edge);
            }
        }
    }

    @Override
    public Iterable<Edge> edges() {
        return mst;
    }

    @Override
    public double weight() {
        double x = 0;
        for(Edge edge : mst){
            x += edge.getWeight();
        }
        return x;
    }
}
